﻿/*
 
C# implementation of Shunting yard algorithm (http://en.wikipedia.org/wiki/Shunting_yard_algorithm)
====================================================================================================
Author of the source code: Martin Vseticka, 2008

Following text (extract of article above) contains only parts that are implemented:
 
 The algorithm in detail
 
 11:     * While there are tokens to be read:
 12: 
 13:         * Read a token.
 14:         * If the token is a number, then add it to the output queue.
 15:         * If the token is an operator, o1, then:
 16: 
 17:             * while there is an operator, o2, at the top of the stack, and o1 is associative or left-associative and
 18:               its precedence is less than (lower precedence) or equal to that of o2 pop o2 off the stack, onto the output queue
 19:             * push o1 onto the stack.
 20: 
 21:         * If the token is a left parenthesis, then push it onto the stack.
 22:         * If the token is a right parenthesis:
 23: 
 24:             * Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
 25:             * Pop the left parenthesis from the stack, but not onto the output queue.
 26: 
 27:     * When there are no more tokens to read:
 28: 
 29:         * While there are still operator tokens in the stack:
 30:             * Pop the operator onto the output queue.
 31:     * Exit.
 32: */
 
 using System;
 using System.Collections;
 using System.Text;
 
  namespace ConsoleApplication1
  {
      class Program
      {
          static void Main(string[] args)
          {
              // input
              string input = Console.ReadLine(); // in the form: 1<space>+<space>2<space>/<space>2
  
              Hashtable ht = new Hashtable();
              // operators with the precedence in parsing math expressions
              ht.Add("+", 1); ht.Add("-", 1); ht.Add("*", 2); ht.Add("/", 2);
              string[] tokens = input.Split(' ');
              string output = "";
  
              ArrayList operator_stack = new ArrayList();
  
              int number = 0;
  
              for (int i = 0; i < tokens.Length; i++)
              {
  
                  if (int.TryParse(tokens[i], out number))
                  {
                      output += tokens[i] + " ";
                      continue;
                  }
  
                  if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
                  {
                      while (operator_stack.Count > 0 && (string)operator_stack[operator_stack.Count - 1]!="(" &&
                            (int)ht[tokens[i]] <= (int)ht[(string)operator_stack[operator_stack.Count - 1]])
                      {
                          output += tokens[i] + " ";
                          operator_stack.RemoveAt(operator_stack.Count - 1);
                      }
  
                      operator_stack.Add(tokens[i]);
                      continue;
                  }
  
                  if (tokens[i] == "(")
                  {
                      operator_stack.Add(tokens[i]);
                      continue;
                  }
  
                  if (tokens[i] == ")")
                  {
                      while ((string)operator_stack[operator_stack.Count - 1] != "(")
                      {
                          output += operator_stack[operator_stack.Count - 1] + " ";
                          operator_stack.RemoveAt(operator_stack.Count - 1);
                      }
                      operator_stack.RemoveAt(operator_stack.Count - 1); // delete "("
                      continue;
                  }
              } // for cyclus
  
              while (operator_stack.Count > 0)
              {
                  output += operator_stack[operator_stack.Count - 1] + " ";
                 operator_stack.RemoveAt(operator_stack.Count - 1);
             }
 
 
             Console.WriteLine("Postfix notation of the given expression in infix notation is: {0}", output);
             Console.ReadLine();
         }
     }
 }
